package com.cet.qz.unit01.chapter1_3;

import edu.princeton.cs.algs4.StdIn;

/**
 * @program: algorithm
 * @description: 补全缺少左括号的表达式
 *                  例如：1+2)*3-4)*5-6))) --> ((1+2)*((3-4)*(5-6)))
 *                  思路解析：此题可参考带括号表达式求值的思路
 * @author: 陈恩涛
 * @create: 2021-04-03 21:23
 **/
public class Qz1_3_9 {



    public static void fixExpression(String exp) {

        //算数符号栈
        Stack<String> ops = new Stack<>();

        //数栈
        Stack<String> nums = new Stack<>();

        for (int i = 0; i < exp.length(); i++) {
            String s = exp.substring(i, i + 1);
            if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
                ops.push(s);
            } else if (")".equals(s)) {
                String val2 = nums.pop();
                nums.push("("+nums.pop() + ops.pop() + val2 + s);
            } else {
                nums.push(s);
            }
        }

        System.out.println("表达式修复后为："+nums.pop());
    }

    public static void main(String[] args) {
        System.out.println("请输入一个缺省( 的表达式：");
        String exp = StdIn.readString();
        fixExpression(exp);
    }
}
